package elementaryAlgorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

/**
 * @author 郭辉
 * @className TODO
 * @description 78. 子集
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 *
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 * 示例 2：
 *
 * 输入：nums = [0]
 * 输出：[[],[0]]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 10
 * -10 <= nums[i] <= 10
 * nums 中的所有元素 互不相同
 * 通过次数606,290提交次数747,865
 * @date 2023/4/4 16:13
 * @company 海康威视
 * @since 1.0.0
 */
public class Leet78 {
    Set<Set<Integer>> res = new HashSet<>();
    public List<List<Integer>> subsets(int[] nums) {
        int[][] numsSec = new int[nums.length][nums.length];
        for (int i = 0; i < nums.length; i++) {
            int[] ints = Arrays.copyOfRange(nums, 0, nums.length );
            numsSec[i] = ints;
        }
        sets(numsSec,0,0,new ArrayList<>());
        List<List<Integer>> sRes = new ArrayList<>();
        Iterator<Set<Integer>> iterator = res.iterator();
        while (iterator.hasNext()){
            Set<Integer> next = iterator.next();
            Iterator<Integer> iterator1 = next.iterator();
            List<Integer> tem = new ArrayList<>();
            while (iterator1.hasNext()){
                Integer next1 = iterator1.next();
                tem.add(next1);
            }
            sRes.add(tem);
        }
        return sRes;
    }
    //返回条件
    //选择
    //路径
    public void sets(int nums[][], int row, int col,List<Integer> track ){
        //返回条件
        Set<Integer> tem = new HashSet<>();
        tem.addAll(track);
        res.add(tem);
        if (track.size() == nums.length){
            return;
        }

        for (int i = col; i < nums.length; i++) {
            //剪枝
            if (track.contains(nums[i][i])){
                continue;
            }
            //选择
            track.add(nums[row][i]);
            sets(nums,row+1,col+1,track);
            //撤销
            track.remove(track.size()-1);
        }
    }


//    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsetsSec(int[] nums) {
        dfs(0, nums,new ArrayList<>());
        return ans;
    }

    public void dfs(int cur, int[] nums, List<Integer> track) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(track));
            return;
        }
        track.add(nums[cur]);
        dfs(cur + 1, nums,track);
        track.remove(track.size() - 1);
        dfs(cur + 1, nums,track);
    }


    public static void main(String[] args) {
        Leet78 leet78 = new Leet78();
        int[] param = {1,2,3};
        System.out.println(leet78.subsetsSec(param));
    }

}
